package student.duing.wangli;

import java.util.ArrayList;
import java.util.List;

/**
 * 子集的异或总和 再求和
 */
public class SubSetXORSum {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3};
        List<List<Integer>> result = buildSubSets(nums);
        System.out.println(result);
        System.out.println("==============");
        int answer = subsetXORSum(nums);
        System.out.println(answer);
    }

    /**
     * 解法一：
     * 思路：先求出 条件数组的 所有子集
     * 每个子集中的 元素 相异或 除空集和单个值 的子集
     * 最后 将所有值相加
     */
    public static int subsetXORSum(int[] nums) {
        //存储最终加和的结果
        int result = 0;
        //分别存储 空集 单个值的子集 以及 多个值的子集
        int empty = 0, one = 0, other = 0;
        //求所有子集
        List<List<Integer>> subs = buildSubSets(nums);
        for (List<Integer> sub : subs) {
            if (sub.size() == 0) {
                //空集
                empty = empty ^ 0;
            } else if (sub.size() == 1) {
                //单个值的子集
                for (Integer integer : sub) {
                    one += integer ^ 0;
                }
            } else {
                //其他子集
                int tmp = 0;
                for (int i = 0; i < sub.size(); i++) {
                    //单个集合 累异或
                    tmp ^= sub.get(i);
                }
                other += tmp;
            }
        }
        result = empty + one + other;
        return result;
    }


    //求给定数组的  所有子集
    public static List<List<Integer>> buildSubSets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //先添加一个空集
        result.add(new ArrayList<>());
        //遍历条件数组
        for (int i = 0; i < nums.length; i++) {
            //获取当前子集个数
            int size = result.size(); // 1  2
            //依次取出当前子集 并为每一子集 添加元素nums[i]
            //最后再添加回result
            for (int j = 0; j < size; j++) {
                List<Integer> sub = new ArrayList<>(result.get(j));
                sub.add(nums[i]);
                result.add(sub);
            }
        }
        return result;
    }


}
